/*

* Seth Simon, Jay'Neisha Jackson, Andrew Pomnean, Christopher Snyder

* memoryManager.c

*

* Compilation instructions: gcc -std=c99 -o memoryManager memoryManager.c -lm

*

* Changes in the last revision:

*              ##########################################

*              NOTE THE NEW COMPILATION INSTRUCTIONS!!!!!

*              ##########################################

*

*             text_size + data_size + heap_size == total_size is now only checked
*				if the policy is segmentation, rather than for both policies

added failed_allocations variable
changed main function to increment said variable appropriately (only works for paging)
program will not exit for a failed allocation with paging

*

*/





#include <stdio.h> 

#include <ctype.h> 

#include <stdlib.h> 

#include <string.h> 

#include <errno.h>

#include <math.h>



// GLOBAL VARIABLES:

// #################



enum boolean{FALSE,TRUE}; 

enum POLICY{SEGMENTATION,PAGING};



int policy = -1; // 0/SEGMENTATION is segmentation, 1/PAGING is paging, -1 is if the 

//memory manager has not yet been initialized. 

char *error_message; //if a function fails, this will point to the error message 

int lineNumber = 0; //line number currently being processed in the input file

int totSize=0;
int failed_allocations = 0; //number of failed allocations due to not enough memory



struct hole {

	int start;

	int size;

	int pid;

	char type;

	struct hole *next;

	struct hole *prev;

	int physical_page_number; //irrelevant if seg. is the policy

} *hole_list; //for paging, this could be called a list of free pages



struct page {

	int virtual_page; //virtual page number

	int physical_page; //corresponds to this physical page number

	struct page *next;

	int used; //number of bytes of this page that are in use 

};



struct process {

	int pid;

	int size[4]; //size[0] is total size, [1] is text size, [2] is data size, [3] is 

	//heap size

	struct process *next;

	struct process *prev;

	int start[3]; //for segmentation, starting address of text, data, and heap 

	//segments (respectively). For paging, the starting address is irrelevant

	struct page *page_map; 

} *process_list;

struct process *list; 
struct hole *hlist;

// FUNCTION PROTOTYPES:

// ####################



int initialize(int,int); //initialize with (argument 1) bytes of memory, using policy 

//(argument 2 (0 for seg., 1 for paging)).

//Returns 1/TRUE for success, 0/FALSE for failure



int allocate(int,int,int,int,int); // allocate (argument 1) bytes of memory to the 

//process with pid (argument 2), with (argument 3), (argument 4), and (argument 5)

// bytes for the text, data, and heap segments (respectively). returns 1/TRUE for 

//success, 0/FALSE for failure.



int deallocate(int); //deallocate the memory that was allocated to the process with pid 

//(argument 1). returns 1/TRUE for success, 0/FALSE for failure.



int printMemoryState(); //prints current state of memory, as instructed in the project 

//handout.



int checkProgramSyntax(int,char **); //checks syntax of the arguments given to this 

//program. returns FALSE/0 if the syntax is bad, and puts the error message in

// the error_message variable. Otherwise, returns 1/TRUE.



int checkSyntax(char *); //checks the syntax of any line in the input file. Only checks 

//that the number of arguments is correct, and that the arguments that should be

// integers are integers. Returns 0/FALSE and puts an error message in the global 

//variable if the syntax is bad. Returns 1/TRUE is the syntax is correct.



char *trimWhiteSpace(char *); //trim whitespace from the beginning and end of a string, 

//returns the new string



struct hole *removeHole(int); //removes (argument 1) bytes of the first hole from the hole list.

// takes care of updating hole pointers, and sorting the hole list.

// returns the hole structure that was removed, or if the size demand is too big, returns NULL



struct process *addProcess(void); //add a process to the end of the process_list; return said process.

//Initializes the prev & next pointers, but does not initialize anything else



void sortHoleList(void); //sorts hole_list



struct page *addPage(struct process *); //adds a page_map entry to this process and return said entry.



struct process *findProcess(int); //finds a process by using (argument 1), which is the pid. returns NULL if not found.



void removeProcessFromList(struct process *); //removes a process from process_list. Updates EVERYTHING: such as page map,

//list pointers, and frees the segmentation space



void releasePages(struct process *); //puts a process' used pages back into hole_list.



void releaseMemory(int,int); //adds the memory starting at (argument 1) and whose size is (argument 2) back into the hole list.

//takes care of keeping the hole list sorted. This function is for segmentation only.



struct hole *addHole(int,int); //adds a hole that starts at (argument 1) and whose size is (argument 2) to the hole_list



int lookForNeighborHoles(struct hole *, struct hole **, struct hole **); //Looks for holes that neighbor (argument 1) in physical memory.

//Stores the first found hole address in (argument 2), and the second found hole address in (argument 3). Returns the number of holes found.



int mergeHoles(struct hole *,struct hole *,struct hole *); // (argument 1) is a hole. (argument 2) is either its left or right neighbor.

// (argument 3) is its other neighbor. If it only has one neighbor, then make argument 3 the following: (struct hole *) 0

//returns TRUE on success, FALSE on failure



// MAIN FUNCTION: 

// ##############



int main(int argc, char **argv) {

	if(!checkProgramSyntax(argc,argv)) {

		printf("Error: %s\n",error_message);

		exit(1);

	}



	char line[1024]; //stores a line from the input file

	strcpy(line,"");



	FILE *input;

	if(!(input = fopen(argv[1],"r"))) {

		printf("Error: Unable to open file %s\n",argv[1]);

		exit(1);

	}

	list=(struct process*)malloc(sizeof(struct process));
	(*list).next=0;
	hlist=(struct hole*)malloc(sizeof(struct hole));
	(*hlist).next=0;

	while(fgets(line,1023,input)) { //while not EOF

		lineNumber++;

		if(!checkSyntax(line)) {

			printf("Error: Line %d: %s contents %s\n",lineNumber,error_message,line);

			exit(1);

		}



		if(isdigit(*line)) { //then this is the initialization statement

			int arg1 = atoi(trimWhiteSpace(strtok(line," ")));

			int arg2 = atoi(trimWhiteSpace(strtok(NULL," ")));

			totSize=arg1;

			if(!initialize(arg1,arg2)) {

				printf("Error: Line %d: %s\n",lineNumber,error_message);

				exit(1);

			}

		}



		else if(*line == 'A' || *line == 'a') { //allocation statement

			int args[5];

			strtok(line," "); //get rid of the "A"



			for(int i = 0; i < 5; i++) { 

				args[i] = atoi(trimWhiteSpace(strtok(NULL," ")));

			}



			if(!allocate(args[0],args[1],args[2],args[3],args[4])) {
				if(strcmp(error_message,"Insufficient memory.") == 0) {
					failed_allocations++;
					continue;
				}

				printf("Error: Line %d: %s\n",lineNumber,error_message);

				exit(1);

			}

		}



		else if(*line == 'D' || *line == 'd') { //deallocation statement

			strtok(line," "); //get rid of the "D"

			int arg = atoi(trimWhiteSpace(strtok(NULL," ")));

			if(!deallocate(arg)) {

				printf("Error: Line %d: %s\n",lineNumber,error_message);

				exit(1);

			}

		}



		else if(*line=='P' || *line=='p') {

			if(!printMemoryState()) {

				printf("Error: Line %d: %s\n",lineNumber,error_message);

			}

		}



		else { //syntax error in input file

			printf("Error: Line %d: Syntax error\n",lineNumber);

			exit(1);

		}

	} //end while not EOF


	return 0; 

} //end main 





// USER-DEFINED FUNCTIONS: 

// #######################



// Initialize: 

// ###########



int initialize(int bytes, int pol) { 

	policy = pol;

	hole_list = (struct hole *) malloc(sizeof(struct hole));

	process_list = (struct process *) malloc(sizeof(struct process));



	if(pol != SEGMENTATION && pol != PAGING) {

		error_message = "Second argument is invalid.";

		return FALSE;

	}



	else if(pol == PAGING && bytes % 32 != 0) {

		error_message = "Physical memory must be a multiple of 32 for paging";

		return FALSE;

	}



	if(policy == SEGMENTATION) {

		hole_list->start = 0;

		hole_list->size = bytes;

		hole_list->next = NULL;

		hole_list->prev = NULL;



		process_list->page_map = NULL;

		process_list->next = NULL;

		process_list->prev = NULL;

		process_list->size[0] = 0; //to indicate that this entry in the linked list is unused



	}

	else if(policy == PAGING) {

		//populate hole_list:

		hole_list->prev = NULL;

		struct hole *cur_hole = hole_list;

		int cum_size = 0;



		for(; cum_size < bytes; cum_size += 32) {

			cur_hole->start = cum_size;

			cur_hole->size = 32;

			cur_hole->physical_page_number = (int) cum_size/32;



			struct hole *prev = cur_hole;

			cur_hole->next = (struct hole *) malloc(sizeof(struct hole));

			cur_hole = cur_hole->next;

			cur_hole->prev = prev;

		}

		cur_hole = NULL;

		//populate process_list:

		process_list->page_map = NULL;

		process_list->next = NULL;

		process_list->prev = NULL;

		process_list->size[0] = 0; //to indicate that this entry in the linked list is unused.

	}



	return TRUE; 

}



// Check Program Syntax: 

// #####################



int checkProgramSyntax(int argc,char **argv) { 

	if(argc != 2) {

		error_message = "Usage: memoryManager (input file)\n";

		return FALSE;

	}

	return TRUE; 

}



//Check Syntax: 

// ############



int checkSyntax(char *original_line) { 

	char line[strlen(original_line) + 1];

	strcpy(line,original_line);

	char *arguments[7];

	arguments[0] = trimWhiteSpace(strtok(line," "));



	for(int i = 1; i < 7; i++) {

		if(!(arguments[i] = trimWhiteSpace(strtok(NULL," ")))) {

			break;

		}

	}



	if(strlen(arguments[0]) != 1 && !isdigit(*arguments[0])) {

		error_message = "First argument is invalid";

		return FALSE;

	}



	//for checking that certain arguments are integers:

	char *endp = '\0';

	int required[2]; //required[0] is the first index of the arguments array that 

	//must be an integer. required[1] is the last index that must be an integer.



	//check that number of arguments is correct:

	switch(*arguments[0]) {

	case 'a':

	case 'A':       if(arguments[6] || !arguments[5]) { //if too many or not 

		//enough arguments

		error_message = "Wrong number of arguments.";

		return FALSE;

				 }

				 required[0] = 1;

				 required[1] = 5;

				 break;

	case 'd':

	case 'D':       if(arguments[2] || !arguments[1]) { //if too many or not enough arguments

		error_message = "Wrong number of arguments.";

		return FALSE;

				 }

				 required[0] = 1;

				 required[1] = 1;

				 break;

	case 'p':

	case 'P':       if(arguments[1]) {

		error_message = "Too many arguments.";

		return FALSE;

				 }

				 required[0] = 0;

				 required[1] = -1;

				 break;

	case '0':

	case '1':

	case '2':

	case '3':

	case '4':

	case '5':

	case '6':

	case '7':

	case '8':

	case '9':       if(arguments[2] || !arguments[1]) {

		error_message = "Wrong number of arguments.";

		return FALSE;

				 }

				 required[0] = 0;

				 required[1] = 1;

				 break;

	default:        error_message = "First argument is invalid";

		return FALSE;

		break;

	}







	//check that the arguments that should be integers are integers:

	for(int i = required[0]; i < required[1] + 1;i++) { 

		int value = (int) strtol(arguments[i],&endp,10);

		if(endp == arguments[i] || *endp || errno == ERANGE) {

			error_message = "Invalid argument";

			return FALSE;

		}

	}

	return TRUE;



}



// Trim White Space: 

// #################



char *trimWhiteSpace(char *argument) {

	//CASES TO DEAL WITH:

	//1. "        " (all whitespace)

	//2. "    a   " first non-whitespace char = last non-whitespace char

	//3. "  bb    " typical situation

	//4. argument==NULL



	if(!argument) //case 4

		return argument;



	char *result = malloc(strlen(argument)+1);



	//find first non-whitespace character:

	int first = 0; // *(result+0) is first non-whitespace char

	char *ptr = argument;

	while(*ptr && isspace(*ptr))

		ptr++;



	if(*ptr == '\0') //deals with unexpected/strange case 1

		return "";



	first = ptr - argument;



	//find last non-whitespace character:

	int last = strlen(argument) - 1;

	ptr = argument + last;

	while(ptr >= argument && isspace(*ptr))

		ptr--;



	last = ptr - argument;



	//generate the result string:



	int i;

	for(i = first;i <=last; i++) //case 2 and 3 are handled fine in this loop

		*(result + i - first) = *(argument + i);



	*(result + i - first) = '\0';

	return result;

} 

void empty(struct hole *curHol,int empList[256][2]) {
	int count=0;
	int i=0;
	int j=0;
	memset(empList[0],0,256);
	memset(empList[1],0,256);
	while ((*curHol).next!=0 | count==0) {
		if ((*curHol).pid==0) {
			empList[j][0]=(*curHol).start;
			empList[j][1]=(*curHol).size;
			j=j+1;
		}
		if ((*curHol).next!=0) {
			curHol=(*curHol).next;
		}
		else {
			count=count+1;
		}
		i=i+1;
	}
}


// Allocate: 

// #########            

int allocate(int bytes,int pid,int text_size,int data_size,int heap_size) {

	if(text_size + data_size + heap_size != bytes && policy==SEGMENTATION) {

		error_message = "Inconsistent size arguments.";
		failed_allocations=failed_allocations+1;

		//Returned True  instead of false because I don't want to skip allocating the process with inconsistent arguments and continue
		return TRUE;

	}



	//Paging

	if (policy == PAGING) {

		int bytesRemaining = bytes;



		//populate some of the process data:

		struct process *newProcess = addProcess();

		newProcess->pid = pid;

		newProcess->size[0] = bytes;

		newProcess->size[1] = text_size;

		newProcess->size[2] = data_size;

		newProcess->size[3] = heap_size;

		newProcess->next = NULL;



		for(int i = 0;bytesRemaining > 0;i++, bytesRemaining -= 32) {

			struct hole *free_hole;

			if(!(free_hole = removeHole(32))) {

				error_message = "Insufficient memory.";

				return FALSE;

			}



			struct page *page_map = addPage(newProcess);

			page_map->virtual_page = i;

			page_map->physical_page = free_hole->physical_page_number;

			page_map->next = NULL;

			page_map->used = (bytesRemaining < 32) ? bytesRemaining : 32;

		}



	} //end if policy is paging



	//Segmentation

	else if(policy == SEGMENTATION) {
		//Iterate the list linked list the last node is reached
		struct process *current,*previous;
		current=list;
		previous=0;
		if (current!=0) {
			previous=current;
			if ((*current).next!=0) {
				while ((*current).next!=0) {
					previous=current;
					current=(*current).next;
				}
			}

			if ((*current).next==0 && (*current).size[0]!=0) {
				(*current).next=(struct process*)malloc(sizeof(struct process));
				previous=current;
				current=(*current).next;
				(*current).prev=previous;
			}

			if ((*current).next==0 && (*previous).size[0]==0) {
				(*current).next=0;
				(*current).prev=0;
			}               
		}

		//Set the values of the current process
		(*current).pid=pid;
		(*current).size[0]=bytes;
		(*current).size[1]=text_size;
		(*current).size[2]=data_size;
		(*current).size[3]=heap_size;

		struct hole *curHole;
		curHole=hlist;
		//If the first hole is empty
		if ((*curHole).size==0) {
			//Text
			(*curHole).size=text_size;
			(*curHole).start=0;
			(*curHole).prev=0;
			(*curHole).next=(struct hole*)malloc(sizeof(struct hole));
			(*curHole).pid=pid;
			(*curHole).type='t';

			//Data
			(*(*curHole).next).prev=curHole;
			curHole=(*curHole).next;
			(*curHole).start=(*(*curHole).prev).start+(*(*curHole).prev).size;
			(*curHole).size=data_size;
			(*curHole).pid=pid;
			(*curHole).type='d';

			//Heap
			(*curHole).next=(struct hole*)malloc(sizeof(struct hole));
			(*(*curHole).next).prev=curHole;
			curHole=(*curHole).next;
			(*curHole).start=(*(*curHole).prev).start+(*(*curHole).prev).size;
			(*curHole).size=heap_size;                              
			(*curHole).pid=pid;
			(*curHole).type='h';

			//Empty Node
			(*curHole).next=(struct hole*)malloc(sizeof(struct hole));
			(*(*curHole).next).prev=curHole;
			curHole=(*curHole).next;
			(*curHole).start=(*(*curHole).prev).start+(*(*curHole).prev).size;
			(*curHole).next=0;
			(*curHole).size=totSize-(*curHole).start;
			(*curHole).pid=0;
		}

		//Other wise
		else {
			//create a double integer array with pid,start and size
			int holes[256][2];

			int i;
			int j;
			int count=0;
			j=0;
			i=0;

			//This function adds the empty holes to the holes double int array
			empty(curHole,holes);

			//order the holes array from largest to smallest size
			i=0;
			j=1;
			int largest;
			largest=holes[i][1];
			int pos=i;
			int temp[2];
			temp[0]=0;
			temp[1]=0;
			int start=holes[i][0];
			while (holes[i][1]!=0) {
				while (holes[j][1]!=0) {
					if (largest<holes[j][1]) {
						largest=holes[j][1];
						pos=j;
						start=holes[j][0];
					}
					j=j+1;
				}
				temp[0]=holes[i][0];
				temp[1]=holes[i][1];
				holes[i][0]=start;
				holes[i][1]=largest;
				holes[pos][0]=temp[0];
				holes[pos][1]=temp[1];
				i=i+1;
				j=i+1;
			}

			int sizes[2];
			i=0;
			j=0;
			pos=1;
			int sizes2[2];
			sizes2[0]=(*current).size[1];
			sizes2[1]=(*current).size[2];
			sizes2[2]=(*current).size[3];

			//Compare the sizes of heap text and data in the process size array
			//array of integers ordering heap data and text from largest size to address 0 holding the positon of the largest value and address 2 holding the position of the 
			//smallest value
			largest=sizes2[i];
			pos=0;
			while (i<3) {
				while (j<3) {
					if (sizes2[j]>largest) {
						largest=sizes2[j];
						pos=j;
					}
					j=j+1;
				}
				sizes2[pos]=0;
				sizes[i]=pos;
				largest=0;
				j=0;
				i=i+1;
			}

			i=0;
			j=0;
			sizes2[0]=text_size;
			sizes2[1]=data_size;
			sizes2[2]=heap_size;

			curHole=hlist;
			count=0;
			//Need to notify the user of an error and quit the program if one of the data segments are too big or the start is invalid and quit the program
			int allocStatus;
			allocStatus=0;
			while (i<3) {
				int fragment=0;
				while ((*curHole).next!=0 | count==0) {
					if ((*curHole).start==holes[0][0]) {
						fragment=(*curHole).size-sizes2[sizes[i]];
						if (fragment<0) {
							printf("There is insufficient memory in the system for process %d\n",pid);
							deallocate(pid);
							failed_allocations=failed_allocations+1;
							allocStatus=1;
							break;
						}

						//Change the pid of the current whole to indicate that it now contains a process
						(*curHole).pid=pid;
						//set the type of curHole
						if (sizes[i]==0) {
							(*curHole).type='t';
						}
						if (sizes[i]==1) {
							(*curHole).type='h';
						}
						if (sizes[i]==2) {
							(*curHole).type='d';
						}
						//If there would be more than 16 bytes left after this process is added to the current node, create a new node
						if (fragment>16) {
							//add a new node whose start is the previous nodes start+size, next is 0, size is total_size-start
							struct hole *prevNext;
							(*curHole).size=sizes2[sizes[i]];
							prevNext=(*curHole).next;
							(*curHole).next=(struct hole*)malloc(sizeof(struct hole));
							(*(*curHole).next).prev=curHole;
							(*(*curHole).next).pid=0;
							(*(*curHole).next).start=(*(*(*curHole).next).prev).start+(*(*(*curHole).next).prev).size;

							//If the nodes original next value is null, there isn't a node after it so add a node to the end of the list
							if (prevNext==0) {
								(*(*curHole).next).size=totSize-(*(*curHole).next).start;
							}

							//otherwise add the node between this node and the next node
							else {
								(*(*curHole).next).next=prevNext;
								(*(*(*curHole).next).next).prev=(*curHole).next;
								(*(*curHole).next).size=(*(*(*curHole).next).next).start-(*(*curHole).next).start;
							}

						}

						if ((*curHole).next!=0) {
							curHole=(*curHole).next;
						}

						else {
							count=count+1;
						}

						break;
					}

					if ((*curHole).next!=0) {
						curHole=(*curHole).next;
					}

					else {
						count=count+1;
					}
				}

				//Allocation failed
				if (allocStatus==1) {
					break;
				}

				curHole=hlist;
				empty((*curHole).next,holes);
				i=i+1;
			}
		}

	} //end else if policy is segmentation

	else { //policy isn't seg. and policy isn't paging

		error_message = "Memory Manager has not been initialized.";

		return FALSE;

	}

	return TRUE;

}



// Deallocate: 

// ###########

int deallocate(int pid) { 

	if(policy == SEGMENTATION) {

		int i=0;

		struct process *current;

		current=list;

		struct process *previous;



		//If the first value is the value to be removed



		if (current!=0) {

			if ((*current).pid==pid) {

				//Can't remove the first node without loosing the list so

				//copy the values from the next node then remove the next node

				if ((*current).next!=0) {
					(*current).pid=(*(*current).next).pid;

					(*current).size[0]=(*(*current).next).size[0];

					(*current).size[1]=(*(*current).next).size[1];

					(*current).size[2]=(*(*current).next).size[2];

					(*current).size[3]=(*(*current).next).size[3];

					(*current).next=(*(*current).next).next;

					if ((*current).next!=0) {
						(*(*current).next).prev=current;
					}

					(*current).prev=0;

				}

				else {
					(*current).pid=0;

					(*current).size[0]=0;

					(*current).size[1]=0;

					(*current).size[2]=0;

					(*current).size[3]=0;

					(*current).next=0;

					(*current).prev=0;

				}

			}

		}

		if ((*current).next!=0) {
			current=(*current).next;
		}

		else {
			current=0;
		}

		//While the current value is not an empty node
		while (current!=0) {

			//Set the previous variable to the current values previous variable
			if ((*current).prev!=0) {
				previous=(*current).prev;
			}

			else {
				previous=0;
			}

			//If the current values pid is the pid to be removed

			if ((*current).pid==pid) {
				//printf("In here\n");

				//If the current values previous value is not 0
				if (previous!=0) {
					//Move the current values previous values next to the value after current
					if ((*current).next!=0) {
						(*previous).next=(*current).next;
					}


					else {
						(*previous).next=0;

					}
				}

				if ((*current).next!=0) {
					(*(*current).next).prev=previous;
				}


				(*current).next=0;

			}

			if ((*current).next!=0) {
				current=(*current).next;
			}

			else {
				current=0;
			}

		}


		//change pid to zero in hole list and merege with any surrounding zero values

		struct hole *curHole,*prevHole;

		curHole=hlist;

		int prevChange;

		while (curHole!=0) {

			prevChange=0;

			if ((*curHole).pid==pid) {

				(*curHole).pid=0; 

				if ((*curHole).prev!=0 && (*(*curHole).prev).pid==0) {

					//The the next value of the current holes previous pointer now equals the current holes next pointer

					(*(*curHole).prev).next=(*curHole).next;

					//The size of the value at the current holes previous pointer is now the size of the current hole + the size of the previous hole

					(*(*curHole).prev).size=(*curHole).size+(*(*curHole).prev).size;

					//The previous value of the current hole's next pointer now points to the current holes previous value

					(*(*curHole).next).prev=(*curHole).prev;

					//The hole that is being removed's next and previous values are now equal to zero

					prevHole=curHole;

					curHole=(*curHole).prev;

					(*prevHole).next=0;

					(*prevHole).prev=0;

					prevChange=1;

				}

				//If the value after the current value is empty merge them

				if ((*curHole).next!=0 && (*(*curHole).next).pid==0) {

					//The current holes size equals its current size plus the size of the next value

					(*curHole).size=(*curHole).size+(*(*curHole).next).size;

					//The current holes next pointer is set to the the node after it's next node

					prevHole=(*curHole).next;

					(*curHole).next=(*(*curHole).next).next;

					//The node that is being deleted has its next and prev pointers set to zero

					(*prevHole).next=0;

					(*prevHole).prev=0;

					//The value at the current hole's new next pointer has it previous value set to the current node

					if ((*curHole).next!=0) {
						if (curHole!=0) {
							(*(*curHole).next).prev=curHole;
						}
					}

				}
			}



			if (curHole!=0) {
				if ((*curHole).next!=0) {
					curHole=(*curHole).next;
				}

				else {
					curHole=0;
				}
			}

		} 


		return TRUE;

	}



	else if(policy == PAGING) {

		struct process *proc;

		if(!(proc = findProcess(pid)))

			return FALSE;



		removeProcessFromList(proc);

		return TRUE;

	}

	else { //policy is neither seg. nor paging

		error_message = "Memory Manager has not been initialized.";

		return FALSE;

	}

}







// Print Memory State:

// ###################



//edited by Andrew Pomnean

// Print Memory State:

// edited again by Seth (policy variable can be used, print variable is unnecessary)

// ###################

int printMemoryState() {
	printf("\nPRINTING MEMORY STATE:\n");

	//paging

	if (policy == PAGING){

		//calculate policy-independent statistics:
		int totalmem = totSize;
		int totalpages = totSize / 32;

		//calculate size of free memory and number of holes/free pages:

		struct hole *cur = hole_list;

		int free_memory = 0;

		int free_holes = 0;

		while(cur != NULL) {

			free_memory += cur->size;

			if (cur->next != NULL) {

				free_holes++;

				cur = cur->next;

			}

			else {break;}

		}





		//calculate size of used memory and number of processes:

		struct process *curp = process_list;

		int used_memory = 0;

		int processCount = 0;



		while(curp != NULL) {

			if(curp->next != NULL){

				used_memory += ((policy==SEGMENTATION) ? curp->size[0] : (int)ceil(curp->size[0]));
				processCount++;
				curp = curp->next;
			}

			else {break;}

		}



		//calculate total memory:

		int total_memory = used_memory + free_memory;

		int total_pages = (int) total_memory/32;

		int allocated_pages = totalpages - free_holes;



		//populate list of free pages:

		int free_page_list[free_holes];

		cur = hole_list;

		for(int i = 0;i < free_holes && cur;i++,cur = cur->next) { 

			free_page_list[i] = (int) ((cur->start)/32);                               
		}



		printf("Memory Size = %d bytes, total pages = %d\n",totalmem,totalpages);

		printf("allocated pages = %d, free pages = %d\n",allocated_pages,free_holes);

		printf("There are currently %d active process(s).\n",processCount);

		printf("Free Page list:\n");

		for(int i=0;i<free_holes;i++) {

			if(i+1==free_holes)
				printf("%d\n",free_page_list[i]);

			else
				printf("%d, ",free_page_list[i]);
		}



		printf("Process list:\n");

		curp = process_list;

		for(;curp;curp = curp->next) { //for each process

			int numPages = (int) curp->size[0]/32 + ((curp->size[0]%32 == 0) ? 0 : 1);

			printf(" process id=%d, size=%d bytes, number of pages=%d\n",curp->pid,curp->size[0],numPages);

			for(struct page *paige = curp->page_map;paige;paige = paige->next) { //for each page in this process

				printf("\tVirt Page %d -> Phys Page %d\tused: %d bytes\n",paige->virtual_page,paige->physical_page,paige->used);

			}

		}

		printf("\nFailed allocations (No memory) = %d\n",failed_allocations);

		return TRUE;

	}



	//segmentation

	if (policy == SEGMENTATION) {
		int total;
		total=totSize;
		struct hole *curHole;
		curHole=hlist;
		int alloc=0;
		int free=0;
		int holes=0;
		struct process *proc;
		proc=list;
		int procs=0;

		while (curHole!=0) {
			if ((*curHole).pid!=0) {
				alloc=alloc+(*curHole).size;
			}
			else {
				free=free+(*curHole).size;
			}
			holes=holes+1;
			curHole=(*curHole).next;
		}

		while (proc!=0) {
			procs=procs+1;
			proc=(*proc).next;
		}


		printf("Memory Size = %d bytes, allocated bytes = %d , free = %d \n",total,alloc,free);

		printf("There are currently %d holes and %d active process(s).\n",holes,procs);

		curHole=hlist;
		proc=list;

		int count=1;

		printf("Hole List\n");

		while (curHole!=0) {
			printf("Hole %d: Start Location %d Size %d PID %d\n",count,(*curHole).start,(*curHole).size,(*curHole).pid);                                    
			curHole=(*curHole).next;
			count=count+1;
		}

		curHole=hlist;

		printf("\nProcess List\n");

		while (proc!=0) {
			printf("Process ID = %d, Size = %d allocation = %d\n",(*proc).pid,(*proc).size[0],(*proc).size[1]+(*proc).size[2]+(*proc).size[3]);
			while (curHole!=0) {
				if ((*curHole).pid==(*proc).pid && (*curHole).type=='t') {
					printf("        Text start = %d, size = %d\n",(*curHole).start,(*proc).size[1]);
					break;
				}
				curHole=(*curHole).next;
			}

			curHole=hlist;

			while (curHole!=0) {
				if ((*curHole).pid==(*proc).pid && (*curHole).type=='d') {
					printf("        Data start = %d, size = %d\n",(*curHole).start,(*proc).size[3]);
					break;
				}
				curHole=(*curHole).next;
			}

			curHole=hlist;

			while (curHole!=0) {
				if ((*curHole).pid==(*proc).pid && (*curHole).type=='h') {
					printf("        Heap start = %d, size = %d\n",(*curHole).start,(*proc).size[2]);
					break;
				}
				curHole=(*curHole).next;
			}


			curHole=hlist;

			proc=(*proc).next; 
			count=count+1;


		}
		printf("\n Failed allocations (no memory): %d\n",failed_allocations);

		/*printf("Hole list: \n");

		cur = hole_list;

		for(int i=1;cur && i<=free_holes;i++,cur=cur->next)

		printf("Hole %d: start location = %d, size = %d\n",i,cur->start,cur->size);


		printf("\nProcess list: \n");

		curp = process_list;

		while(curp) {

		printf("process  id=%d,  size=%d,  allocation=%d\n",curp->pid,curp->size[0],curp->size[0]);

		printf("\ttext start=%d, size=%d\n",curp->start[0],curp->size[1]);

		printf("\tdata start=%d, size=%d\n",curp->start[1],curp->size[2]);

		printf("\theap start=%d, size=%d\n",curp->start[2],curp->size[3]);

		curp = curp->next;

		}

		//printf("\nFailed allocations (No memory) = %i");*/

		return TRUE;
	}

	if (policy!=SEGMENTATION && policy!=PAGING) { //policy is neither seg nor paging

		error_message = "Memory Manager is not initialized.";

		return FALSE;

	}


	// PAGING Example:

	// Memory size = 1024 bytes, total pages = 32

	// allocated pages = 6, free pages = 26

	// There are currently 3 active process

	// Free Page list:

	//   2, 6, 7, 8, 9, 10, 11, 12...

	// Process list:

	//  Process id=34, size=95 bytes, number of pages=3

	//    Virt Page 0 -> Phys Page 0  used: 32 bytes

	//    Virt Page 1 -> Phys Page 3  used: 32 bytes

	//    Virt Page 2 -> Phys Page 4  used: 31 bytes

	//  Process id=39, size=55 bytes, number of pages=2

	//    Virt Page 0 -> Phys Page 1  used: 32 bytes

	//    Virt Page 1 -> Phys Page 13  used: 23 bytes

	//  Process id=46, size=29 bytes, number of pages=1

	//    Virt Page 0 -> Phys Page 5  used: 29 bytes

	//

	// Failed allocations (No memory) = 2

	;

}



// Remove Hole:

// ############



struct hole *removeHole(int size) {



	if(!hole_list) { //0 holes left; hole_list == NULL

		error_message = "Insufficient memory.";

		return NULL;

	}

	if(size > hole_list->size) {

		error_message = "Insufficient memory.";

		return NULL;

	}

	else if(size == hole_list->size) {

		struct hole *retVal = hole_list;

		hole_list = hole_list->next;

		if(hole_list)

			hole_list->prev = NULL;

		return retVal;

	}

	else { //size < hole_list->size, this will not execute unless policy is segmentation

		//split first hole into 2 holes:

		struct hole *hole3 = hole_list->next; //third hole in the list, hole3 could be NULL



		struct hole *hole2 = (struct hole *) malloc(sizeof(struct hole));

		hole2->start = hole_list->start + size;

		hole2->size = hole_list->size - size;



		struct hole *hole1 = (struct hole *) malloc(sizeof(struct hole));

		hole1->start = hole_list->start;

		hole1->size = size; //hole 1 is the hole to be removed



		hole2->prev = NULL;

		hole2->next = hole3;

		if(hole3) {

			hole3->prev = hole2;

		}

		hole_list = hole2;



		sortHoleList();



		return hole1;

	}

}



//Add Process:

//############



struct process *addProcess(void) {

	struct process *last_proc = process_list; //the last process in the process list

	if(last_proc->size[0] == 0) { //then the process list has only one entry, which is unused.

		return last_proc;

	}



	while(last_proc->next) {

		last_proc = last_proc->next;



	}



	last_proc->next = (struct process *) malloc(sizeof(struct process));

	last_proc->next->prev = last_proc;

	last_proc = last_proc->next;

	last_proc->next = NULL;



	return last_proc;

}



//Sort Hole List:

//###############

void sortHoleList(void) { //selection sort, for now, I guess

	if(!hole_list || !(hole_list->next)) //aka there are 0 or 1 holes, then it's already sorted

		return;



	struct hole *largestHole = hole_list;

	int largestSize = hole_list->size;



	struct hole *startingHole = hole_list;

	int change = TRUE;



	struct hole *currentHole = hole_list;



	while(startingHole && startingHole->next) {

		if(!change) {

			startingHole = startingHole->next;

		}

		currentHole = startingHole;

		largestHole = currentHole;

		largestSize = currentHole->size;

		change = FALSE;

		while(currentHole) {

			if(currentHole->size > largestSize) {

				change = TRUE;

				largestHole = currentHole;

				largestSize = currentHole->size;

			}

			currentHole = currentHole->next;

		}

		if(change) { //then put it before the starting hole

			if(largestHole->prev) {

				largestHole->prev->next = largestHole->next;

			}

			if(largestHole->next) {

				largestHole->next->prev = largestHole->prev;

			}

			largestHole->next = startingHole;

			largestHole->prev = startingHole->prev;

			if(startingHole->prev)

				startingHole->prev->next = largestHole;

			startingHole->prev = largestHole;

			if(!(largestHole->prev))

				hole_list = largestHole;

		}

	}



}



//Add Page:

//#########



struct page *addPage(struct process *proc) {

	if(!proc->page_map) {

		proc->page_map = (struct page *) malloc(sizeof(struct page));

		return proc->page_map;

	}

	struct page *last_page = proc->page_map;

	while(last_page->next) {

		last_page = last_page->next;

	}

	last_page->next = (struct page *) malloc(sizeof(struct page));

	return last_page->next;

}



//Find Process:

//#############

struct process *findProcess(int pid) {

	if(process_list->size[0] == 0) { //then the process list is empty

		error_message = "Process not found";

		return FALSE;

	}

	struct process *result = process_list;

	for(;result && result->pid != pid;result = result->next); //go through every entry in the process list,

	//break if end of list is reaches or result is found



	if(!result) {

		error_message = "Process not found.";

		return NULL;

	}

	return result;

}



//Remove Process From List:

//#########################

void removeProcessFromList(struct process *proc) {

	//update pointers:

	if(proc->prev)

		proc->prev->next = proc->next;

	if(proc->next)

		proc->next->prev = proc->prev;

	if(proc == process_list) {

		process_list = proc->next;
		if(!process_list) { //bugfix: if statement added by Seth
			process_list = (struct process *) malloc(sizeof(struct process));
			process_list->size[0] = 0;
		}
	}



	if(policy == PAGING)

		releasePages(proc);

	else { //then policy is SEGMENTATION

		for(int i=0;i<3;i++)

			releaseMemory(proc->start[i],proc->size[i+1]);

	}

}



//Release Pages:

//##############

void releasePages(struct process *proc) {

	struct page *paige = proc->page_map;

	for(;paige;paige = paige->next) {

		//get page's info, and use it to add to the hole list

		int hole_start = paige->physical_page * 32;

		addHole(hole_start,32);

	}

}



//Release Memory:

//###############

void releaseMemory(int start,int size) {

	addHole(start,size);

}



//Add Hole:

//#########

struct hole *addHole(int start,int size) {

	struct hole *whole = (struct hole *) malloc(sizeof(struct hole));

	hole_list->prev = whole;

	whole->start = start;

	whole->size = size;

	whole->next = hole_list;

	whole->prev = NULL;

	hole_list = whole;

	if(policy == SEGMENTATION) {

		struct hole *neighbor1;

		struct hole *neighbor2;

		int retval = lookForNeighborHoles(whole,&neighbor1,&neighbor2);

		if(retval == 2) {

			mergeHoles(whole,neighbor1,neighbor2);

		}

		else if(retval == 1) {

			mergeHoles(whole,neighbor1,(struct hole *)0);

		}

		sortHoleList();

	}

	else

		hole_list->physical_page_number = (int) start/32;

}



//Look for Neighbor Holes:

//########################



int lookForNeighborHoles(struct hole *whole, struct hole **dest1, struct hole **dest2) {

	int retVal = 0;

	int target_end = whole->start; // leftneighbor->start + size == target_end

	int target_start = whole->start + whole->size; //rightneighbor->start == target_start

	struct hole *currentHole = hole_list;



	while(currentHole) {

		if(currentHole->start + currentHole->size == target_end) { //then we found the left neighbor

			retVal++;

			if(retVal == 1)

				*dest1 = currentHole;

			else

				*dest2 = currentHole;

		}

		else if(currentHole->start == target_start) { //then we found the right neighbor

			retVal++;

			if(retVal == 1)

				*dest1 = currentHole;

			else

				*dest2 = currentHole;

		}

		currentHole = currentHole->next;

	}

	return retVal;

}



//Merge holes:

//############



int mergeHoles(struct hole *middle,struct hole *neb1,struct hole *neb2) {

	//1: merge middle with each neighbor, one at a time



	for(int i=0;i<2;i++) {

		if(i == 1)

			neb1 = neb2;

		if(i==1 && !neb2)

			break;





		//is middle to the left or right of neb?

		if(neb1->start + neb1->size == middle->start) { // in physical memory, neb1 is to the left of middle

			//remove neb1, and modify middle's values (and the linked list pointers)



			//fix pointers:

			if(neb1->prev)

				neb1->prev->next = neb1->next;

			if(neb1->next)

				neb1->next->prev = neb1->prev;



			//fix middle's values:

			middle->start = neb1->start;

			middle->size += neb1->size;



			//what about the hole's physical_page_number variable?

			//Don't worry about it, you never merge holes in paging

		}

		else if(neb1->start == middle->start + middle->size) { //in physical memory, middle is to the left of neb1

			//remove neb1, and modify middle's values (and the linked list pointers)



			//fix pointers:

			if(neb1->prev)

				neb1->prev->next = neb1->next;

			if(neb1->next)

				neb1->next->prev = neb1->prev;



			//fix middle's values:

			//middle->start stays the same

			middle->size += neb1->size;

		}

		else { //neb1 is not a neighbor!

			error_message = "Programmer Bug.";

			return FALSE;

		}

	} //end for

	return TRUE;

}
